import java.util.ArrayList;
import java.util.List;

public class letterCombinations {
    List<String> list = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0){
            return list;
        }
        String[] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        a(digits,numString,0);
        return list;
    }
    StringBuilder s = new StringBuilder();
    public void a(String digits,String[] numsString,int num){
        if(num == digits.length()){
            list.add(s.toString());
            return;
        }
        String str = numsString[digits.charAt(num) - '0'];
        for(int i = 0;i < str.length(); i++){
            s.append(str.charAt(i));
            a(digits,numsString,num+1);
            s.deleteCharAt(s.length()-1);
        }
    }
}
